/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-13
 * Time: 17:54
 */

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        //先判断是否有环,这样代码更简洁
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                //一个从相遇节点开始走
                //另一个从头开始
                //相遇的位置就是环的入口
                while(fast!=head){
                    fast=fast.next;
                    head=head.next;
                }
                return head;
            }
        }
        return null;
    }
}
